МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
ЗВІТ
до лабораторної роботи № 4
на тему:
" Структура даних ЧЕРГА "
з дисципліни: "Програмування, частина 3(Структури даних та алгоритми)"
Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
Iндивiдуальне завдання :
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Варіант №26
Змоделювати чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву.
Хід роботи:
Результат виконання програми :
/
Текст програми:
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
void FirstOut(int *d, int s)
{
d[0] = NULL;
for (int i = 0; i < s; i++)
{
d[i] = d[i + 1];
}
}
void main() {
setlocale(LC_ALL, "ukr");
int var,
data[10] = {0 },
queueArray[10],
queueArraySize = 0,
queueSize = 0;
queue<int> intQueue, Queue3, queueSort;
cout << "Додати в чергу : " << endl;
// Створення масиву для черги
for (int i = 0; i < 10; i++) {
cin >> queueArray[i];
queueArraySize++;
}
//Створення черги
for (int counter = 0; counter < queueArraySize; counter++) {
if (queueArray[counter] > 0) {
intQueue.push(queueArray[counter]);
queueSize++;
}
else
intQueue.pop();
}
for (int i = 0; i < queueArraySize; i++)
{
data[i] = intQueue.front();
intQueue.pop();
}
for (int i = 0; i < queueArraySize; i++)
{
cout << data[i] << " ";
//intQueue.pop();
}
/*int j = 0;
data[0] = NULL;
j++;
for (int i = 0; i < queueArraySize; i++)
{
data[i] = data[i + 1];
// data[queueArraySize] = NULL;
//intQueue.pop();
}
data[0] = NULL;
j++;
}*/
int j = 0;
FirstOut(data, queueArraySize);
j++;
FirstOut(data, queueArraySize);
j++;
FirstOut(data, queueArraySize);
j++;
cout << "\n\n\n";
for (int i = 0; i < queueArraySize - j; i++)
{
cout << data[i] << " ";
}
system("pause");
}
Висновок: на лабораторній роботі №4, я ознайомився зі структурою даних ЧЕРГА.
